package com.leet.code.lcof;


import java.util.LinkedList;
import java.util.List;

public class Code36 {
    public static void main(String[] args) {

        int[] s = {4, 2, 6, 1, 3, 5, 7};
        Node treeNode = getTreeByArray(s);
        inorder(treeNode);
        Code36 code = new Code36();
        Node node = code.treeToDoublyList(treeNode);
        l = node.left;
        f = node;

        inorder(node);
    }

    static Node l;
    static Node f;

    public static void inorder(Node rootNode) {
        if (rootNode.left != null) {
            if (rootNode.right == f) {
                return;
            }
            inorder(rootNode.left);

        }

        System.out.print(rootNode.val + ",");
        if (rootNode.right != null) {
            if (rootNode.left == l) {
                return;
            }
            inorder(rootNode.right);
        }
    }


    Node last;
    Node first;

    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        prc(root);
        first.left = last;
        last.right = first;
        return first;
    }

    public void prc(Node node) {
        if (node.left != null) {
            prc(node.left);
        }
        if (last != null) {
            last.right = node;
        } else {
            first = node;
        }
        node.left = last;
        last = node;
        if (node.right != null) {
            prc(node.right);
        }
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }


    public static Node getTreeByArray(int[] arr) {
        List<Node> treeNodes = new LinkedList<>();
        Node treeNode = new Node(arr[0]);
        treeNodes.add(treeNode);
        getTreeByArray(arr, 1, treeNodes);
        return treeNode;
    }

    public static void getTreeByArray(int[] arr, int i, List<Node> treeNodes) {


        if (treeNodes == null || treeNodes.size() == 0) {
            return;
        }

        List<Node> list = new LinkedList<>();

        for (Node treeNode : treeNodes) {
            if (i >= arr.length) {
                return;
            }
            treeNode.left = new Node(arr[i++]);
            if (i >= arr.length) {
                return;
            }
            treeNode.right = new Node(arr[i++]);
            list.add(treeNode.left);
            list.add(treeNode.right);
        }

        getTreeByArray(arr, i, list);

    }

}
